/*
Basic Calculator II Total Accepted: 4949 Total Submissions: 27373 My Submissions Question Solution
Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

*/

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
	bool isOperand(char c)
	{
		if (c-'0'>=0&&c-'0'<=9)
		{
			return true;
		}
		return false;
	}
	int calculate(string s) {
		if (s.size()==0)
			return 0;

		stack<int> stackInt;
		
		for (int i = 0; i < s.size(); i++)
		{
			char temp = s[i];
			if (isOperand(temp))
			{
				int cur = temp - '0';
				while (i+1 < s.size()&&isOperand(s[i+1]))
				{
					cur = 10 * cur + (s[++i] - '0');
				}

				if (!stackInt.empty()&&(stackInt.top() ==2 || stackInt.top()==3))
				{
					int op1 = stackInt.top();
					stackInt.pop();
					int op2 = stackInt.top();
					stackInt.pop();

					int res = 0;
					if (op1==2)
					{
						res = op2*cur;
					}
					else
					{
						res = op2 / cur;
					}

					stackInt.push(res);
				}
				else
				{
					stackInt.push(cur);
				}

			}
			else if (temp ==' ')
			{
				continue;
			}
			else
			{
				switch (temp)
				{
				case '+':stackInt.push(0);
					break;
				case '-':stackInt.push(1);
					break;
				case '*':stackInt.push(2);
					break;
				case '/':stackInt.push(3);
					break;
				default:
					return -1;
				}
			
			}
		}

		if (stackInt.empty())
		{
			return 0;
		}

		stack<int> stack1;
		while (!stackInt.empty())
		{
			int temp = stackInt.top();
			stack1.push(temp);
			stackInt.pop();
		}
		stackInt = stack1;

		int res = stackInt.top();
		stackInt.pop();

		while (!stackInt.empty())
		{
			int op = stackInt.top();
			stackInt.pop();
			int opr = stackInt.top();
			stackInt.pop();
			if (op==0)
			{
				res += opr;
			}
			else
			{
				res -= opr;
			}
		}
		return res;
	}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

int main(int argc, char* argv[])
{
	int A = 0, B = 0, C = 0, D = 0, E = -1, F = -1, G = 1, H = 1;

	string str = "0*1";

	Solution s;
	int result;

	result = s.calculate(str);

	//int n = 7;
	//ifs1.countPrimes(val);

	//strRes = s.findRepeatedDnaSequences(s1);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s1.containsNearbyAlmostDuplicate(vecInt, 1, 2))
	//	cout << " True" << endl;
	//else
	//cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;s
/*
//string s1 = "GAGAGAGAGAGA";
string s1 = "GAGAGAGAGAGA";
vector<string> strRes;

TreeNode *root = new TreeNode(1);
TreeNode *left1 = new TreeNode(2);
TreeNode *left2 = new TreeNode(5);

TreeNode *right1 = new TreeNode(3);
TreeNode *right2 = new TreeNode(4);

root->left = left1;
left1->right = left2;

root->right = right1;
right1->right = right2;

//vector<char> level1({ '1', '1', '1', '1', '0' });
//vector<char> level2({ '1', '1', '0', '1', '0' });
//vector<char> level3({ '1', '1', '0', '0', '0' });
//vector<char> level4({ '0', '0', '0', '0', '0' });


vector<vector<char>> grid;
grid.push_back(level1);
grid.push_back(level2);
grid.push_back(level3);
grid.push_back(level4);ss
ListNode *head = new ListNode(1);
ListNode *head1 = new ListNode(2);
ListNode *head2 = new ListNode(6);
ListNode *head3 = new ListNode(3);
ListNode *head4 = new ListNode(4);
ListNode *head5 = new ListNode(5);

ListNode *head6 = new ListNode(6);

head->next = head1;
head1->next = head2;
head2->next = head3;
head3->next = head4;
head4->next = head5;
head5->next = head6;
int val = 6;
char a1[] = { '1', '0', '1', '0', '0' };
char a2[] = { '1', '0', '1', '1', '0' };
char a3[] = { '1', '1', '1', '1', '1' };
char a4[] = { '1', '0', '0', '1', '0' };

vector<char> level1(a1, a1 + sizeof(a1) / sizeof(char));
vector<char> level2(a1, a1 + sizeof(a1) / sizeof(char));
vector<char> level3(a1, a1 + sizeof(a1) / sizeof(char));
vector<char> level4(a1, a1 + sizeof(a1) / sizeof(char));

vector<vector<char> > martix;
martix.push_back(level1);
martix.push_back(level2);
martix.push_back(level3);
martix.push_back(level4);

Solution s;
int result;
result = s.maximalSquare(martix);
*/
